The disclosed invention generally relates to vector to raster converters for raster type plotters, printers, cathode ray tube displays, and other display systems which utilize rasterized data, and is more particularly directed to an efficient, high-speed vector to raster conversion technique which utilizes look-up tables for raster data.
As is well known, a raster display system, such as an electrostatic printer or a video display, provides images by printing or illuminating selected ones of addressable dots or pixels arranged in rows and columns called a raster matrix. Display data for each pixel (e.g., printed or blank) must be provided, and can be stored, for example, in a bitmap memory where the display information for each pixel is located at a predetermined memory location. That is, a given pixel data is associated with the pixel identified by the address where the pixel data is stored. For example, an 8-bit byte might represent the data for 8 contiguous pixels in a row of the raster for a one color display.
Plot information for plotters is often represented by a plurality of line segments, where each line segment is represented by a vector which identifies the characteristics of the line segment, such as start location, slope, and length. For example, plot data can be entered in a computer plotting system by using a computer graphics language, similar to entering a computer program. From the entered plot data, appropriate software generates vectors representing the plot, which are stored. It should be readily appreciated that vector data requires considerably less storage than the corresponding raster data.
For raster plotters, vector information must be converted to raster data. Depending on the system utilized, such conversion can be performed prior to printing of the plot or while the plot is being printed. For several reasons, many systems perform the conversion while printing. The printer would otherwise be idle if vector to raster conversion had to be completed prior to plotting, and vector data can be processed to provide usable raster data that can be plotted while vector-to-raster conversion takes place. Moreover, the amount of data storage required for storing raster data for an entire plot can be very large.
Known techniques for vector to raster conversion include what are known as digital difference analysis (DDA), major-axis Breshenham, and minor-axis Breshenham techniques. Descriptions of DDA and major-axis Breshenham techniques can be found in textbooks on computer graphics, such as Fundamentals of Interactive Computer Graphics, Foley and van Dam, Addison-Wesley Publishing Company, 1982. Background information on the minor-axis Bresenham algorithm can be found in Run Length Slices for Incremental Lines, J.E. Bresenham et al., IBM Technical Disclosure Bulletin, Vol. 22, No. 8B.
The DDA technique computes the coordinates of the next pixel on the line from the coordinates of the current pixel and the slope m according to: EQU m=(Y2-Y1)/(X2-X1) EQU X[i+1]=X[i]+1 EQU Y[i+1]=Y[i]+m
The pixel at coordinates (X[i+1], ROUND(Y[i+1])), where ROUND identifies the rounding operation, is then chosen to represent the line. Those skilled in the art will appreciate that fixed-point arithmetic must be performed to track the Y coordinate and that the rounding operation is time consuming.
The major-axis Bresenham algorithm avoids these difficulties by using only integer arithmetic. Instead of using a fixed-point accumulator to track the Y coordinate, the algorithm maintains an integer decision variable whose arithmetic sign indicates which of candidate pixels at (X[i+1],Y[i] and (X[i+1],Y[i]+1) should be selected.
Both DDA and the major-axis Bresenham algorithm step along the major axis of the line and generate the raster image one pixel at a time. Bresenham revised his major-axis algorithm to step along the minor axis of the vector and generate the raster image in RUNs of pixels, where a RUN comprises adjacent pixels on the same raster row or column. For shallowly sloped vectors (i.e., vectors with RUNs of many pixels) this technique is more efficient. As the slope of the line approaches one, however, the RUN length (i.e., the number of pixels in a RUN) also approaches one, and the performance of the minor-axis algorithm degenerates to the performance of the major-axis algorithm.
With known vector to raster conversion techniques, throughput is a consideration in that the speed of the plotter might exceed the speed of conversion. Complexity of known techniques is a further consideration.